import java.util.LinkedList;
import java.util.Queue;

class Solution200 {
    public static void main(String[] args) {
        Solution200 solution200  = new Solution200() ;
        char[][] arr = {{'1','1','1','1','0'}
                       ,{'1','1','0','1','0'},
                        {'1','1','0','0','0'},
                        {'0','0','0','0','0'}}; 
        solution200.numIslands(arr);
    }
    private int rest  = 0 ; 
    private int[] dx = {0, 0, 1 , -1};
    private int[] dy = {1 , -1 , 0 , 0} ; 
    private Queue<int[]> queue = new LinkedList<>();
    private int m , n ;
    public int numIslands(char[][] grid) {
        m = grid.length ;
        n = grid[0].length ;
        for(int i=0 ; i < m ; i ++){
          for(int j=0 ; j < n ; j ++){
            if(grid[i][j] == '1'){
                rest ++ ;
              bfs(grid) ; 
            }
          }
        }
        return rest ;
    }
    private void bfs(char[][]grid){
       while(!queue.isEmpty()){
          int[] ret = queue.poll() ;
          int a = ret[0] , b = ret[1] ; 
          grid[a][b] = '0' ; 
          for(int i=0 ; i < 4 ; i ++){
             int x = a +dx[i] , y = b+dy[i] ;
             if(x >=0 && x < m && y >=0 && y < n && grid[x][y]=='1'){
                queue.add(new int[]{x , y}) ; 
             }
          }
       }
    }
}